package leetcode_day._2021._202105._2131;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/23 9:55
 * 与数组中元素的最大异或值
 * 算法：位运算  字典树
 * 暴力解法 --- 超时
 * ----------------------------
 * 与 421 题差不多
 * 只不过加了一个条件，要求数组中的元素要小于 queries 中的元素
 * 先把 nums 排序，然后再把 queries 按照第二个元素排序
 * 这样就确保了遍历 queries 时，字典树的中的数字都是小于 queries[i][1] 的
 */
public class _23_1707 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new _23_1707().maximizeXor_perfect(new int[]{0, 1, 2, 3, 4},
                new int[][]{{3, 1}, {1, 3}, {5, 6}})));
    }

    public int[] maximizeXor(int[] nums, int[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            int max = Integer.MIN_VALUE;
            for (int num : nums) {
                if (num <= query[1]) {
                    int tmp = num ^ query[0];
                    max = max > tmp ? max : tmp;
                }
            }
            ans[i] = max == Integer.MIN_VALUE ? -1 : max;
        }
        return ans;
    }

    class Trie {
        Trie[] node = new Trie[2];
        void add(int x) {
            Trie cur = this;
            for (int i = 31; i >= 0; i--) {
                int u = (x >> i) & 1;
                if (null == cur.node[u]) cur.node[u] = new Trie();
                cur = cur.node[u];
            }
        }
        int get(int x) {
            Trie cur = this;
            int res = 0;
            for (int i = 31; i >= 0; i--) {
                int a = (x >> i) & 1;
                // 有最优二进制，就或上 1，这样结果就为 1
                if (cur.node[a ^ 1] != null) {
                    res |= 1 << i;
                    a ^= 1;
                }
                cur = cur.node[a];
            }
            return res;
        }
    }
    public int[] maximizeXor_perfect(int[] nums, int[][] queries) {
        Trie trie = new Trie();
        // idx 表示 nums 前 idx 个元素被放入字典树中了
        int idx = 0, m = nums.length, n = queries.length;
        int[] ans = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) map.put(queries[i][1], i);
        Arrays.sort(nums);
        Arrays.sort(queries, (a, b) -> a[1] - b[1]);
        for (int[] query : queries) {
            while (idx < m && nums[idx] <= query[1]) trie.add(nums[idx++]);
            // 字典树为空
            if (idx == 0) ans[map.get(query[1])] = -1;
            else ans[map.get(query[1])] = trie.get(query[0]);
        }
        return ans;
    }

}
